Matthias Poloczek
The maximum satisfiability problem (MAX SAT) is a fundamental problem in discrete optimization. Given a collection of clauses with nonnegative weights, our goal is to find an assignment to the variables that satisfies clauses of maximum total weight.
In the first part of the talk we present a simple randomized greedy algorithm that achieves a 3/4 approximation in expectation. In particular, its performance is comparable to Yannakakis' algorithm based on flows and LP (1994) or the LP-rounding algorithm of Goemans and Williamson (1994).
In the second part we explore the limitations of the greedy paradigm using the model of priority algorithms of Borodin, Nielsen, and Rackoff (2003).
On the one hand, we wonder if a better approximation ratio can be obtained by further fine-tuning the assignment probabilities of our algorithm?
On the other hand, we study the question whether our greedy algorithm can be derandomized, and therefore investigate the strength of deterministic greedy algorithms.
Based on joint work with Georg Schnitger, David P. Williamson, and Anke van Zuylen.